package offer_test_60;

import java.util.Arrays;

//从扑克牌中随机抽5张牌，判断是不是顺子，即这5张牌是不是连续的。
//2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意的数字。
public class four_ContinousCards {
	public static void main(String[] args) {
		int[] array = { 0, 4, 6, 9, 0 };
		System.out.println(judge(array));
	}

	public static boolean judge(int[] array) {
		int numofzero = 0;
		int numofgap = 0;
		int[] aftersort = sort(array);
		for (int i = 0; i < aftersort.length; i++) {
			if (aftersort[i] == 0) {
				numofzero++;
			} else {
				if (i + 1 < aftersort.length) {
					if (aftersort[i] == aftersort[i + 1])
						return false;
				}
			}
		}
		int head = numofzero;
		int tail = head + 1;
		while (tail < aftersort.length) {
			if (aftersort[tail] - aftersort[head] > 1) {
				numofgap += (aftersort[tail] - aftersort[head] - 1);
			}
			head++;
			tail++;
		}
		if (numofzero >= numofgap) {
			return true;
		} else {
			return false;
		}

	}

	// 复杂度为On的排序，用于数组中的元素都比较集中，都在[0, max]范围内
	public static int[] sort(int[] array) {
		int max = 0;
		int min = 100;
		for (int i = 0; i < array.length; i++) {
			if (max < array[i])
				max = array[i];
			if (min > array[i])
				min = array[i];
		}
		int[] temp = new int[max - min + 1];
		for (int k : array) {
			temp[k - min] += 1;
		}
		int locate = 0;
		for (int i = 0; i < temp.length; i++) {
			int num = temp[i];
			while (num > 0) {
				array[locate] = i;
				num--;
				locate++;
			}
		}
		return array;
	}
}
